The efficiency of transportation operations is one of the factors having a significant effect on the country's economic growth. A linehaul operation, one of the biggest contributors to the total operating cost of a trucking company, involves moving full loads of less than unit load or full unit load shipments using owner-operator and/or company units.
A review of the prior art revealed that for an optimization procedure to be successful, the following steps have to be executed in sequential order:                (1) Problem definition,        (2) Model development of the problem, and        (3) Solution algorithm development for the model.        
The problem must be defined in the most appropriate manner such that it meets the practical requirements of the real-world problem. This ensures that, when the model is developed, it is a more accurate mathematical representation of the problem. The algorithm developed to meet the requirements of the model can be an existing algorithm, a modified existing algorithm, or a new algorithm developed specifically to solve the model. Since algorithms are usually not developed to solve a specific problem, they require significant modification to address specific operational requirements. If the problem to be solved is a unique problem and cannot be addressed by any of the existing algorithms, it is necessary to develop a new algorithm to meet its requirements.
Some of the existing modeling and solution approaches from recent research that are relevant to linehaul operations are discussed in the following sections of this chapter. There are also some commercially available software packages intended to assist in modeling transportation operation problems, and/or finding a solution to the modeled problem. The advantages and disadvantages of these packages are also discussed in the Commercial Modeling Packages section of this chapter. Although considerable research has been completed in the transport operations area, the scale, nature, and complexity of the current linehaul problem addressed in the present invention is significantly different from ones that have been studied so far and reported in prior art.
The linehaul planning problem and the Vehicle Routing Problem (VRP) in general are non-deterministic polynomial time hard (NP-hard) combinatorial optimization problems for which no efficient algorithms are known that provide a global optimum solution. The solution approaches to NP-hard combinatorial problems can be grouped into two categories, namely exact solution approaches and heuristic solution approaches. The exact solution approach looks into almost every possibility to find the optimum solution and is useful for problems of relatively small size. Heuristic algorithms do not indicate how good the result is in relation to the global optimum, but they are the most practical choice for solving large problems because of the efficiency gains and improvements that they can potentially make.
The Traveling Salesman Problem (TSP) is one of the best known problems in combinatorial optimization (Cook et al., 1998). TSP is a sub-problem of the VRP (Lawler et al., 1992). VRP can have a larger set of solution possibilities, depending on the nature of the problem. The TSP can be described as having N destinations, and the cost, Cij to travel from destination i to j. A salesman (vehicle) starts from the depot to visit each destination once and return back to the depot. The problem is to find the optimal route and the destination visiting order that would yield the minimum total travel cost. If the entire set of solutions were enumerated, the number of calculations would be N! (Taniguchi et al., 2001). Table 2 shows the rapid growth of computational time for solving TSP when N, the number of destinations (customers), increases. In this example, a 10 gigahertz (GHz) processor with basic computation time of 10−10 seconds was used. In an enumeration method, one step may take several computations, but to be conservative, it was treated as if it would take the same time as for one computation. As the following table shows, when N increases from 10 to 50 destinations, computation time to find an exact solution increases from 0.00036 seconds to 9.64*1037 billion years:
Sample SizeComputation Time100.00036seconds207.7years30841111billion years402.59 * 1021billion years509.64 * 1037billion years
Clarke and Wright (1964) developed the earliest heuristic algorithm (that is the Clarke-Wright heuristic algorithm) to solve the VRP. Significant research done to solve the VRP has helped in the development of many heuristic algorithms, which are now commonly used, such as Tabu Search (TS), Simulated Annealing (SA), Genetic Algorithms (GA), and Repeated Descent (RD). Gendreau et al. (1997) applied several heuristics to the VRP and their findings were that the GA, SA, and TS techniques performed significantly well in VRP compared to other algorithms. Wright and Marett (1996) compared the performance of RD, SA, and TS on the TSP and TS outperformed both SA and RD.
Taniguchi et al. (1998) compared the performance of the GA, SA, and TS when applied to the VRP, and concluded that the TS reached the best known solution with the shortest computation time. Reviews on ten of the most common TS heuristics for the VRP with their main features of neighbourhood structures, short term memory, long term memory, and intensification can be found in one of the most recent surveys conducted by Cordeau and Laporte (2002).
The classical VRP is to determine the routes and service order of customers with known demands from a central depot. Although classical VRP models and algorithms cannot be applied to solve linehaul scheduling problems, due to some similarities in the nature of their operations, a survey of the literature pertaining to classical VRP is also included in this chapter. This was done for the purpose of ascertaining what scholars have done to handle similar situations in this subject. It also revealed an understanding of current active research modeling approaches and solution algorithms.
A comprehensive literature survey on the classical VRP and some of its variations was made by Fisher (1995), where he categorized VRP methods into three generations. The first generation consisted of simple heuristics developed in the 60's and 70's, which were mainly based on local search or sweep methods. The second generation included mathematical programming based heuristics (near-optimization algorithms), which differ from normal heuristics in that they include the generalized assignment problems and set partitioning to approximate the VRP. The third and the last generation is the one currently being studied intensively and includes exact optimization algorithms and artificial intelligence methods such as TS, GA, and SA. Christie and Satir (2004) reviewed several existing case studies and found that a 10% to 30% reduction in operational costs is possible through VRP optimization for P & D operations. Satir (2003) analyzed the P & D operations (at a terminal) of a major trucking company in Atlantic Canada, and compared the potential efficiency gains of implementing an optimization system. The results of the case study showed that operational costs could be reduced by as much as 50%.
The classical VRP is not applicable (without additional constraints and considerable modification) to real-world transportation operation problems. One of the problems closest in nature to the classical VRP is that of parcel P & D. In most P & D operations vehicles have various fixed capacities and can serve customers (with varying demands) only within this capacity. This type of problem is referred to as the Capacitated VRP (CVRP) in literature. In most real-world transportation problems, customers have certain time windows within which they have to be served by a fleet of vehicles of varying capacities. This type of CVRP with time windows (TW) is known as VRPTW. The VRPTW has many practical applications such as in LTL P & D from a central depot or multiple depots. Tan et al. (2000) investigated various third generation heuristic methods such as TS, SA, and GA to solve the VRPTW.
Although the classical VRP and some of its variations have been studied extensively in literature, VRP with FTL (VRPFTL) has received relatively less attention in literature. The closest VRP variations to VRPFTL are the multi-depot vehicle scheduling problem with time windows (MDVSPTW) and the multi-trip vehicle routing and scheduling problem (MTVRSP), which have been studied comparatively more. The main difference between VRPFTL and MDVSPTW is that while VRPFTL has one FTL demand per trip (one customer), MDVSPTW can have one or more customer demands to fill the truck per trip. Brandao (1997) points out that the MTVRSP has additional constraints to the VRPTW such as a vehicle can make more than one trip, vehicle's capacity is considered in terms of both volume and weight, the access to some customers is restricted to some vehicles, and driver's schedule must comply with the driving regulations. Desaulniers et al. (1998) published a paper on MDVSPTW and waiting costs, which bears some similarities to the problem addressed in this present invention. A literature survey was also made by Desrosiers et al. (1995) for multi-depot VRP related problems. A recent VRPFTL paper published by Arunapuram et al. (2003) introduced new techniques that were intended to solve such problems with exact solutions, which use a branch-and-bound algorithm to solve an integer-programming formulation of the VRP.
Yang et al. (2004) published a paper which considered various costs associated with empty miles, delayed completion times, and job rejection when using real time information to improve productivity. Liu et al. (2003) developed a heuristic algorithm to determine a mixed truck delivery system that allows both hub-and-spoke and direct shipment delivery modes. Smilowitz et al. (2003) studied the possible integration of longhaul operations for package delivery services, which has similar context to some of the components of the problem addressed in the present invention.
Trucking operations consist of P & D and linehaul operations. The classical VRP is applicable primarily to P & D operations. Although a considerable amount of research on the classical VRP exists in literature, relatively less research has been done on vehicle scheduling and planning for linehaul operations. Planning and scheduling of transportation operations has potential applications in the rail, maritime, trucking, and airline modes of transportation. Some of the real-world problems, models proposed, applications, and implementation benefits pertaining to planning and scheduling in literature are discussed in this section.
Linehaul planning is more challenging than the typical VRP in that the fleet of vehicles has to satisfy each terminal's varying demands from every other terminal, whereas in the classical VRP, it has to satisfy customer demands only from a central terminal. One of the most similar problems to linehaul planning is that of airline planning and scheduling. Significant research has been undertaken in this area, and OR has had a significant impact on the airline industry. Clarke and Smith (2004) point out that American Airlines had an estimated cost savings of approximately $18 million USD per year (relative to previously used enumeration methods) by implementing an optimization-based crew pairing system in 1989. Cook (2000) claims that American Airlines testified that over $500 million was generated annually in incremental profits due to their optimized schedule planning system. In a similar manner, when the Delta Airlines first implemented their fleet assignment module in 1992, the planning group reported an approximate cost savings of more than $100,000 USD per day (Subramaniam, 1994). These cost savings increased as planners gained more experience and confidence with the module, and reached an estimated $200,000 USD per day in late 1993. Ryan et al (2001) reported not only an increase in savings of more than $15,655,000 NZ per year in crew scheduling costs at Air New Zealand, but also an increase in crew member satisfaction.
Many of the problems found in maritime, railway, and airline transportation operations are based on multi-commodity flow problems. A multi-commodity flow problem is defined in the Algorithms and Theory of Computation Handbook as “a maximum-flow problem (finding the maximum flow between any two vertices of a directed graph) involving multiple commodities, in which each commodity has an associated demand and source-sink pairs”.
Barnhart et al. (1995) published a partitioning solution procedure to address large-scale multi-commodity flow problems with many commodities. Barnhart et al. (2000) presented a model and iterative solution approach to solve the problem of determining the type of aircraft to assign to each flight and the exact departure time of each flight, given the set of flights with their time windows for a large U.S airline. It should be noted that the process of fleet assignment in airline operations is very similar to tractor assignments in trucking operations, subject to different operational and regulatory constraints.
Barnhart, Hane, and Vance (2000) proposed a branching rule to find a heuristic solution and compared branch-and-price and branch-and-price-and-cut methods to find optimal solutions for highly capacitated problems, specific to telecommunication applications. Barnhart et al. (2002) proposed a new formulation and solution approach that captures network effects and involves the profit maximizing assignment of aircraft types to flight legs.
The general framework for aircraft and crew schedule and planning is given in (Barnhart, 2004). Although decomposing the problem into four subproblems and optimizing them individually would yield a less efficient solution than an overall optimization approach, it is necessary to decompose problems of large size such as linehaul problems in a similar manner to obtain a practical solution in a feasible time.
Toth (2004) stresses the need to undertake planning activities in an efficient way for railway transportation operations and the importance of using computer-aided tools to improve the planning ability of railway systems. He points out some of the problems arising in railway optimization to be line planning, platforming, shunting, locomotive assignment and scheduling, crew scheduling, and train timetabling. In particular, the train timetabling problem, which deals with train scheduling and dispatching, is of similar nature to linehaul planning. Caprara et al. (2002) proposed a graph theoretic formulation to model and solve the train timetabling problem using a directed multigraph in which nodes correspond to departures or arrivals at a certain station at a given instant.
It is also beneficial to understanding the recent research in maritime transportation, since ship routing and scheduling problems are related to linehaul planning problems. Christiansen et al. (2004) reviewed the current status of ship routing and scheduling based on literature published in the last decade. They presented perspectives regarding future developments and use of optimization-based decision-support systems for ship routing and scheduling. They also examined tactical and operational fleet planning operations and consider problems that comprise various ship routing and scheduling aspects. Hooghiemstra et al. (1999) proposed a model for a real ship planning problem, which is a combined inventory management problem and a routing problem with time windows. They also discuss model adjustments to the proposed model to decompose the problem into ship routine and inventory management subproblems. Flatberg et al. (2000) combined an iterative improvement heuristic with an exact solution approach to minimize transportation costs (while ensuring satisfactory inventory levels) within acceptable time limits. The model was for a real-world problem of transporting a single commodity between producing and consuming factories within the same company using a fleet of vessels.
Powel (1996) proposed a stochastic formulation of the dynamic assignment problem with an application to truckload motor carriers where demands arise randomly and continuously throughout the day. Powel et al. (2002) did a case study on implementing operational planning (real-time load matching) model for a trucking carrier. Powel et al. (2000) found that the value of global optimization is lost when users ignore the solution suggested by the model. Crainic and Laporte (1997) discussed some of the main issues in freight transportation operations planning and presented appropriate Operations Research models and methods, as well as computer-based planning tools. They examined the strategic, tactical, and operational decision-making levels and also reviewed significant methodological and instrumental developments in these areas.
The earliest models in freight transportation were deterministic models that captured the time staging of physical activities as against the time staging of information (Powell, 2003). Powell and Carvalho (1998) proposed the use of linear functional approximations to measure the future impact of current decisions in freight transportation planning. Godfrey and Powell (2002) found that non-linear functional approximations produced a better and more stable solution than linear approximations.
Powell et al. (2004) explained a transportation system in terms of the management of the static resources (such as terminals) and passive resources (such as people and equipment) that constrain the system. They also introduced a basic resource model for modeling resources and their attributes. Powell, Shapiro, and Simaõ (2002) formulated a large-scale driver scheduling problem as a multistage dynamic resource allocation problem for an LTL trucking application. The large scale of the problem rendered the use of commercial solvers infeasible. They demonstrated that their techniques provided high quality solutions within reasonable time limits. Powell and Topaloglu (2005) discuss the fleet management problem, which involves managing fleets of equipment to meet the customer requests that arrive randomly over time, often requiring service within a small time window.
Transportation operation problems can be grouped into point-to-point (node) routing and arc routing problems. While in node routing problems the service activity occurs at all (or at some subset of) the nodes, in arc routing problems a single vehicle or a fleet of vehicles must service all (or some subset of) the arcs (and/or edges) of a transportation network (Corberan et al. 2005). The majority of operations fall under the category of point-to-point routing, such as VRP and linehaul operations. Arc routing applications include garbage collection, snow removal, sweeping, gritting, mail delivery, meter reading, school bus routing etc. (Eiselt et al. 1995). Although there are many commercially available packages for arc routing, these packages cannot be used on the current problem, because it is a point-to-point routing problem.
TransCAD is the only software package that fully integrates GIS with demand modeling and logistics functionality (TransCAD 2006). It can be used to solve a variety of logistics problems such as vehicle routing/dispatching, arc routing, and network flow and distribution analysis. Satir (2003) did a case study for real-world P&D operations, using TransCAD to model and solve the problem. The results showed that TransCAD is a very effective scheduling tool for the VRP. However linehaul planning and scheduling problems cannot be solved by using this package.
The ILOG optimization packages are the most popular and considered the de facto optimization standard in OR. The main software components of these optimization packages are: ILOG CPLEX, ILOG Solver, ILOG Dispatcher, and ILOG Scheduler. ILOG (2003) discusses the various components in detail in their respective manuals. A brief description of each of these components from these manuals is summarized in this section.
ILOG CPLEX consists of C, C++, Java, and C# libraries that solve Linear Programming (LP) problems and its extensions such as network flow problems, quadratic programming (QP) problems, quadratically constrained problems, and Mixed Integer Programming (MIP) problems. In MIP problems, any or all of the LP or QP variables are further restricted to take integer values in the optimal solution.
ILOG Solver is a C++ library that allows the user to model optimization problems independently of the algorithms used to solve the problem. The two main techniques for solving the optimization problems are search strategies (Tabu Search or guided local search) and constraint propagation. A comparative study of eight constraint programming languages done by Fernandez and Hill (2003) showed the ILOG Solver to be the fastest, most efficient, and robust.
ILOG Dispatcher is a C++ library that offers features especially designed to solve problems in vehicle routing and maintenance-technician dispatching, This library is made up of classes that represent various aspects of routing plans, their vehicles, visits, and constraints. The Dispatcher finds various applications such as modeling a vehicle routing problem, solving a vehicle routing problem, modeling P & D operations, and routing multiple tours per vehicle. A solution to a routing problem involves the three stages of describing the problem, modeling the problem, and lastly solving the problem by using local search The Dispatcher can also be used to solve a VRP such as an assignment problem, or a P & D problem.
ILOG Scheduler is a C++ library intended to primarily help in solving scheduling and resource allocation problems. It works in conjunction with ILOG Solver and provides specialized modeling and algorithmic enhancements for scheduling problems. ILOG Scheduler makes it feasible to also take temporal and capacity constraints into consideration. The two types of temporal constraints that can be added are precedence constraints and time-bound constraints. While precedence constraints are used when the user needs to specify when an activity must start or end with respect to the start or end time of another activity, time-bound constraints are used to specify when an activity must start or end with respect to a given time.
ILOG CPLEX is not a practical choice for the problem at hand, because the problem requires a MIP formulation, which is extremely processor-intensive and time consuming for a problem of this size. ILOG Dispatcher could not be used for this problem either, because the Dispatcher is specifically designed for P & D type operations.
Using the ILOG Scheduler in conjunction with the ILOG Solver would have been the most appropriate choice to model and solve the problem. However, the problem at hand is not a pure scheduling problem, and has regulatory constraints and operational preferences in addition to the regular operational constraints. The pre-designed modeling environment would make the task of taking these additional regulatory constraints and operational preferences into account very cumbersome.
The latest product from ILOG, which is probably the most appropriate optimization package for linehaul planning is called Transport PowerOps, and was released as recently as April 2005. This package helps planners determine the lowest cost solutions for assigning vehicles, loading shipments and sequencing routes (ILOG PowerOps, 2006). The most important features of PowerOps are that it can handle hours of service regulations, driver rest rules, and multiple time windows. However, a shortcoming of this package is that the current problem requires different fleets to be subjected to different service regulations and for team and single driver vehicles to be handled differently. Some of the other disadvantages of using a package such as PowerOps (besides the company's potential dependency on an external package) are that the model and the operational requirements will have to be updated (building a new model) constantly to accommodate any changes or enhancements made to newer versions of the package, and this would make it difficult to integrate it with the existing IS. Operational preferences which cannot be taken into account by this package at present can be embedded using heuristics. However, this would require significant amount of work in addition to modeling the problem, which by itself is a tedious task. Although this package lacks some features and is not an off-the-shelf package (thus requiring specialized knowledge and expertise to make use of it), it is still a valuable asset to model and optimize linehaul operations.
There is a lack of software specifically designed for linehaul planning and scheduling.